/*
 * =====================================================================================
 *
 *       Filename:  occurcount.cc
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2012年03月15日 15时28分24秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */

#include	<iostream>

const static int upperseq[] = {0,1,2,3,4,5,6,7,8,9};
static int lowereq[10];
static int currcount[10] = {0};

bool success()
{
    int alloccur = 0;
    int i;
    for( i = 0 ; i < 10 ; ++i )
    {
        alloccur += lowereq[i];
        int cnt = 0;
        for( int k = 0 ; k < 10 ; ++k )
        {
            if (lowereq[k] == upperseq[i])
                ++cnt;
        }
        if (lowereq[i] != cnt) 
            break;
    }

    if (i == 10 && alloccur == 10)
        return true;
    return false;
}

void check(int n, int alreadycount)
{
   int limit = 9;
   if (n == -1)
   {
       if (success()) {
           for (int j = 0; j < 10; ++j)
               printf("%d\t",lowereq[j]);
           printf ( "\n" );
       }
       return;
   }

   if (n != 0)
       limit = std::min(10 / n, 9);
   for (int k = currcount[n]; k <= limit; ++k)
   {
       if (alreadycount + k > 10)
           break;
       lowereq[n] = k;
       currcount[k]++;
       alreadycount += k;

       check(n-1, alreadycount);

       currcount[k]--;
       alreadycount -= k;
   }
   return;
}

void countOccurence()
{
    size_t n = sizeof(upperseq) / sizeof(upperseq[0]);
    check(n-1, 0); 
}


int main(int argc, char *argv[])
{
    countOccurence();
}
